package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.LinkedList

/*

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html
https://leetcode.cn/problems/binary-tree-postorder-traversal/
145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]

示例 3：
输入：root = []
输出：[]

示例 4：
输入：root = [1]
输出：[1]
 */
class leetcode_145_Kotlin {
    @Test
    fun test_1() {
        val node: TreeNode = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        node.right = n2
        n2.left = n3

        val actual: List<Int> = preorderTraversal(node)
        val expect: List<Int> = arrayListOf(3, 2, 1)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        val n9 = TreeNode(9)
        n1.left = n2
        n1.right = n3
        n2.left = n4
        n2.right = n5
        n5.left = n6
        n5.right = n7
        n3.right = n8
        n8.left = n9
        val actual: List<Int> = preorderTraversal(n1)
        val expect: List<Int> = arrayListOf(4, 6, 7, 5, 2, 9, 8, 3, 1)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val actual: List<Int> = preorderTraversal(null)
        val expect: List<Int> = ArrayList<Int>()
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_4() {
        val actual: List<Int> = preorderTraversal(TreeNode(1))
        val expect: List<Int> = arrayListOf(1)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    private fun preorderTraversal(root: TreeNode?): List<Int> {
//        return preorderTraversal1(root)
//        return preorderTraversal2(root)
        return postorderTraversal3(root)
    }

    private fun preorderTraversal1(root: TreeNode?): List<Int> {
        val list: ArrayList<Int> = ArrayList<Int>()
        traverse(root, list)
        return list
    }

    private fun traverse(node: TreeNode?, list: ArrayList<Int>) {
        // S - N
        // T - N
        if (null == node) {
            return
        }
        traverse(node.left, list)
        traverse(node.right, list)
        list.add(node.`val`)
    }

    private fun preorderTraversal2(root: TreeNode?): List<Int> {
        val list: ArrayList<Int> = ArrayList<Int>()
        if (null == root) {
            return list
        }
        val stack: LinkedList<TreeNode> = LinkedList<TreeNode>()
        stack.push(root)
        /*
        前序遍历：中左右 => 换左右, 中右左 => 翻转，左右中 (后序遍历)
        stack： 中右左 => 换左右, 中左右 => 翻转 array
         */
        while (!stack.isEmpty()) {
            val node: TreeNode = stack.pop()
            list.add(node.`val`)
            if (null != node.left){
                stack.push(node.left)
            }
            if (null != node.right){
                stack.push(node.right)
            }
        }
        list.reverse()
        return list
    }

    // 统一迭代法
    private fun postorderTraversal3(root: TreeNode?): List<Int> {
        val result: ArrayList<Int> = ArrayList<Int>()
        if (root == null) {
            return result
        }
        val stack: LinkedList<Pair<TreeNode, Boolean>> = LinkedList<Pair<TreeNode, Boolean>>()
        stack.push(Pair<TreeNode, Boolean>(root, false))
        while (!stack.isEmpty()) {
            // 后序遍历 左右中
            val pair: Pair<TreeNode, Boolean> = stack.pop()
            val node: TreeNode = pair.first
            val visited: Boolean = pair.second
            if (visited) {
                result.add(node.`val`)
                continue
            }
            stack.push(Pair<TreeNode, Boolean>(node, true))
            node.right?.let { stack.push(Pair<TreeNode, Boolean>(it, false)) }
            node.left?.let { stack.push(Pair<TreeNode, Boolean>(it, false)) }
        }
        return result
    }
}